// Package day_11_slider_window_monotone_stack demo-03
// @Title day_11_slider_window_monotone_stack
// @Description  二叉树的morris遍历
// @Author  == 琳琳也叫王木木 ==  2021/9/4 19:57
// @Create  2021/9/4 19:57
package day_11_slider_window_monotone_stack

import "fmt"

/**
二叉树的morris遍历

一种遍历二叉树的方式，并且时间复杂度为O(N),空间复杂度为O(1)
通过利用原树中大量空闲指针的方式，达到节省空间的目的
*/

/**
莫里斯遍历的细节
假设来到当前节点cur，开始时cur来到头节点位置
1. 如果当前节点没有左孩子，cur向右移动
2. 如果cur有左孩子，找到左子树上最右的节点mostRight
	a。如果mostRight的右指针指向空，让其指向cur，然后cur向左移动 cur = cur.left
	b. 如果mostRight的右指针指向cur，让其指向nil，然后cur向右移动，cur =cur.Right
3. cur为空时 遍历停止

核心思想:
一个节点如果有左树，会回到当前节点两次！

*/

func Morris(root *TreeNode) {
	if root == nil {
		return
	}
	cur := root
	var mostRight *TreeNode
	for cur != nil {
		mostRight = cur.Left
		if mostRight != nil {
			for mostRight.Right != nil && mostRight.Right != cur {
				mostRight = mostRight.Right
			}
			if mostRight.Right == nil {
				mostRight.Right = cur
				cur = cur.Left
				continue
			} else {
				mostRight.Right = nil
			}
		}
		fmt.Println(cur.Val)
		cur = cur.Right
	}
}
